from typing import *


class Solution:

    def getWordsInLongestSubsequence(self, n: int, words: List[str],
                                     groups: List[int]) -> List[str]:

        def f(i, j):
            if len(words[i]) != len(words[j]):
                return -1
            return sum(a != b for a, b in zip(words[i], words[j]))

        han = [[0] * n for _ in range(n)]
        for i in range(n):
            for j in range(i):
                han[i][j] = han[j][i] = f(i, j)

        from math import inf
        dp = [[1, -1] for _ in range(n)]
        ans = 1
        for i in range(n):
            for j in range(i):
                if len(words[i]) == len(words[j]) and han[i][j] == 1 and groups[i] != groups[j]:
                    if dp[i][0] < dp[j][0] + 1:
                        dp[i][0] = dp[j][0] + 1
                        dp[i][1] = j
                        ans = max(ans, dp[i][0])

        for i in range(n):
            if dp[i][0] == ans:
                k = i
                ret = [0] * ans
                print(type(ret),len(ret))
                while ans > 0:
                    ret[ans - 1]= words[k]
                    k = dp[k][1]
                    ans-=1
                return ret
        return []


s = Solution()
print(
    s.getWordsInLongestSubsequence(n=3,
                                   words=["bab", "dab", "cab"],
                                   groups=[1, 2, 2]))
